1. Field of the Invention
The present invention relates to general interconnect and transmission lines, trees and nets, and methods to obtain their state space models in time domain, and their simulations for their characteristics and evolution, and their practice for various model reduction methods, and optimization methods.
2. Description of the Related Art
With the rapid increase of integration level and speed, IC interconnect has become one of important limiting factors of today's VLSI circuit design performance. It has been commonly recognized that interconnect delay dominates gate delay in current deep submicron VLSI circuits. The average length of the chip interconnect and the chip area occupied by interconnect are both increasing. With the continuous scaling of technology and increased die area, especially the chip operation speed increasing, that situation is becoming worse. The advance of high-speed deep-submicron VLSI technology requires chip interconnect and packaging to be modeled by distributed circuits [Reed and Rohrer, Applied Introductory Circuit Analysis, Prentice Hall, 1999; Wang, patent application Ser. No. 11/037,636, 2005]. Such a detailed modeling level eventually results in large scale linear RLC or RC circuits to be analyzed.
In transmission line area, it is also well know that the transmission line should be modeled as distributed circuits, resulting in large scale linear RLC or RC circuits. When the chip speed is increased fast, the inductor characteristics of interconnect and transmission line, tree and net, denoted in short as ITLTAN, must be considered. For example, in deep submicron interconnects, on-chip inductive effects arising due to increasing clock speeds, increasing interconnect lengths, and decreasing signal rise times. With the continuous development of technology, especially the chip operation speed increasing, that situation becomes an urgent challenge to VLSI performance analysis and design.
In order to design complex VLSI circuits properly, accurate characterization of the interconnect behavior and signal transients is required. That is especially true with VLSI, in which hundreds of thousands of circuit elements can be placed on a single chip, and with ULSI, in which millions of circuit elements can be placed on a single chip. Thus, the need for more accurate and faster modeling technique is not only very desired but also much required in design and analysis. An effort of reducing the circuit order is then necessary in order to evaluate the circuit performance and characteristics in a reasonable time period, as required by real design practice. In circuit design, fast and accurate computer simulation of the behavior of the circuit is important.
Interconnect in a VLSI circuit is usually structured in a tree or a net, especially a tree, where a line as a special tree is a basic component. Thus, the process of characterizing signal waveforms in a tree structured interconnect is of primary importance, after a single line is treated.
There are various model reduction methods, such as Elmore delay model, AWE (Asymptotic Waveform Evaluation) for timing analysis, PVL (Padé approximation via Lanczos approach), Klyrov space decomposition, Klyrov-Arnoldi-based reduced-order modeling, BTM (Balance Truncation Method), and even length-division order (ELO) modeling.
However, all model reduction methods in the state space need to start from an accurate state space high order models in order to result in a good model reduction.
The original accurate models in the state space are important not only as a basis of an accurate starting point for various model reduction methods, but also as a basis of performance comparison for checking the approximation of various model reduction methods.
It is noticed that to get an accurate state space model for the starting point has significantly high computational complexity as shown as follows, in addition to the high computation complexity of model reduction techniques themselves. It is well known that an RC and RLC ITLTAN can be described as the following differential equation in matrix form based on the KCL or KVL:
                                          Gx            ⁡                          (              t              )                                +                                    C              LC                        ⁢                                          ⅆ                                  x                  ⁡                                      (                    t                    )                                                                              ⅆ                t                                                    =                  bu          ⁡                      (            t            )                                              (        1        )            where G and CLC are parameter matrices related to the parameters of resistors, capacitors and inductors of the ITLTAN and its structure, u(t) is the input source vector, and x(t) is a vector of the node voltages and inductor currents or the node voltage derivatives. The state space model {A, B, C, D} of a general ITLTAN is in{dot over (x)}(t)=Ax(t)+Bu(t), y(t)=Cx(t)+Du(t) or y(t)=Cx(t),  (2)where the state variable x(t)εRN, input variable u(t), output variable y(t), the order N is the number of capacitors and inductors in the circuit (ITLTAN), the matrices {A, B, C, D} are the system matrix, input matrix, output matrix and direct output matrix, respectively. Since D=0 as usual, the model may omit D as {A, B, C} in (2). The first equation in (2) is the system equation that is a differential equation, and the second equation in (2) is the output equation that is an algebraic equation. It is known that the BTM based order reduction method needs to start from (2). Furthermore, the motivation of the present invention is not only to provide a starting point for the BTM, but also to provide a new approach for various model reduction methods, and to reveal the characteristics of the ITLTAN, because the system equation determines the dynamics of the ITLTAN circuits, the system matrix determines the characteristics of the ITLTAN circuits, and its eigenvalues determine the time responses to the input signals.
However, it is apparent from equation (1) that the calculation of inverse of matrix CLC, or matrix decomposition (e.g., LU decomposition), and multiplication of CLC−1 with matrix G and vector b, are necessary to get matrix A and matrix B in the state space model. From the well known results, the computation complexity of these approaches is O(N2)˜O(N3) depending on the matrix structure and the approaches. For very high order system, the matrix inverse calculation leads to calculation singularity problem due to bad condition number of the matrix, making a calculation problem. Note that N should be as large as we can for approaching to a distributed model, and on the other hand, it can be in the order of thousands for a typical large industrial tree or net.
It is noticed that the limited number of orders or poles is inappropriate to evaluate the transient response at the nodes of underdamped RLC ITLTAN, which require a much higher order model to accurately capture the transient response. Moreover, highly accurate estimation of signal transients within a VLSI circuit is required for performance-critical models and the ITLTAN, and to accurately anticipate possible hazards during switching.
An exact original high order model is much important not only as a starting point for all model reduction methods, but also as an evaluation criterion for all reduced order models. However, due to very large size of the original model, an important and difficult aspect is how to have a method get its original model in a suitable time and cost-less calculation time.
The way to find this distributed linear model is usually from the s-domain by Kirchhoff's law and algebraic equations, or from the time domain by Kirchhoff's law and differential equations. However, it is bound to meet calculation of so-high dimension matrix inverse in conventional methods. Due to the distributed interconnect characteristics, the size is very large, e.g., a 106×106 matrix, it is desired to have an elegant closed-form of the state space model for the general distributed ITLTAN to dramatically reduce the computation complexity. Moreover, simulations based on these models can be developed to capture the transient response in exact or arbitrary accuracy.
Patent applications (Ser. Nos. 11/037,636 and 11/037,701) of the inventor have presented approaches for generating the state space models by closed forms for RLC and RC interconnect lines respectively. It was the first time to address that open problem by the closed form. Those inventions mainly address a line-structure, i.e., only a special tree-type and/or a component of tree or net structure.
Thus, it is still a broad open problem: how to generate the state space model by its closed form for general ITLTAN. There is no any systematic method to provide state space model via the closed form approach for the general interconnect and transmission tree or net in the literature.
In addition to the above open problem, another question is that: can we present other state space closed form for formulating the state space model of RLC interconnect and transmission lines?
In all, current conventional methods are lack of an elegant way to get exact original high order state space model of the distributed ITLTAN in either tree-structure or net structure.